#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;
typedef unsigned long long ull;
typedef long double ldb;

#define in read()
#define pii pair<int,ll>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back
#define vec vector<int>

int read(){int x = 0,sgn = 1;char ch = getchar();for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);return x*sgn;}

inline bool operator < (pii a,pii b){return a.se * b.fi == b.se * a.fi ? a.fi < b.fi : a.se * b.fi < b.se * a.fi;}

template <typename T>
inline void chkmax(T &x,T y){x = x < y ? y : x;}

const int N = 1e6+10;
const int B = 1e3+10;
const pii I = pii(1,-1);

int n,T,a[N],mx,fa[N],siz[N],cnt,blo[N],bl[B],br[B],totB;
ll lasans,tot;
pii ans[N],val[B];
vec pla[N];

int gf(int x){return fa[x] == x ? x : fa[x] = gf(fa[x]);}

void merge(int x,int y){
	x = gf(x); y = gf(y); if(x == y) return; if(siz[x] < siz[y]) swap(x,y);
	tot -= (ll) siz[x] * siz[x]; tot -= (ll) siz[y] * siz[y];
	siz[x] += siz[y]; fa[y] = x; tot += (ll) siz[x] * siz[x]; cnt--;
}

void Prework(){
	for(int i = 1;i <= n + 1;i++) fa[i] = i,siz[i] = 0,ans[i] = I;
	cnt = 0; tot = 0;
	for(int i = 1;i <= mx;i++){
		if(!pla[i].size()) continue;
		for(int x : pla[i]){
			int l = x - 1,r = x + 1; l = gf(l); r = gf(r); ++cnt; siz[x] = 1; ++tot;
			if(siz[l]) merge(l,x); if(siz[r]) merge(r,x);
		}
		chkmax(ans[cnt],pii(i,tot));
	}
	for(int i = 1;i <= n;i++){
		blo[i] = (i - 1) / B + 1; br[blo[i]] = i;
		if(!bl[blo[i]]) bl[blo[i]] = i;
	}
	totB = blo[n];
	for(int i = 1;i <= totB;i++) val[i] = I;
	for(int i = 1;i <= n;i++) chkmax(val[blo[i]],ans[i]);
}

void getans(int l,int r){
	pii res = I;
	if(blo[l] == blo[r]){
		for(int i = l;i <= r;i++) chkmax(res,ans[i]);
	}else{
		for(int i = l;i <= br[blo[l]];i++) chkmax(res,ans[i]);
		for(int i = blo[l] + 1;i < blo[r];i++) chkmax(res,val[i]);
		for(int i = bl[blo[r]];i <= r;i++) chkmax(res,ans[i]);
	}
	if(res.se == -1) res.fi = -1; printf("%lld %d\n",res.se,res.fi); lasans = 1ll * res.se % n * (res.fi % n) % n;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	n = in; T = in; for(int i = 1;i <= n;i++) a[i] = in,mx = max(mx,a[i]),pla[a[i]].pb(i);
	Prework();
	lasans = 0;
	for(int i = 1;i <= T;i++){
		ll l,r,a = in % n + n,b = in % n + n,x = in % n + n,y = in % n + n;
		l = (a * lasans % n + x - 1) % n + 1; r = (b * lasans % n+ y - 1) % n + 1;
		if (l > r) swap(l, r); ll las = lasans;
		getans(l,r);
		printf("%lld %lld %lld\n",l,r,las % n);
	}
	return 0;
}
